#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define maxn 1010101

struct TreeNode {
    int key, id, pri;
    TreeNode *ch[2];
};
TreeNode *root, *null, tree[maxn];
int n, a, b, tot = 0;

TreeNode *newNode(int x, int id) {
	TreeNode *p = &tree[tot++];
	p->key = x; p->id = id;
	p->pri = rand() * rand();
	p->ch[0] = p->ch[1] = null;
	return p;
}

void rotate(TreeNode *&x, int c) {
    TreeNode *y = x->ch[c];
    x->ch[c] = y->ch[!c];
    y->ch[!c] = x;
    x = y;
}

void insert(TreeNode *&now, TreeNode *node) {
    if (now == null)
		now = node;
    else {
        int t = node->key > now->key;
        insert(now->ch[t], node);
        if (now->ch[t]->pri > now->pri)
			rotate(now, t);
    }
}

void print(TreeNode *x) {
    if (x == null)
    	puts("0");
    else
    	printf("%d\n", x->id);
}

TreeNode *remove(TreeNode *&now, int c) {
    if (now == null || now -> ch[c] == null) {
        TreeNode *p = now;
        now = now->ch[!c];
        return p;
    }
    return remove(now->ch[c], c);
}

int main() {
    null = newNode(0, 0);
    root = null;
    while (scanf("%d",&n),n) {
        if (n == 1) {
            scanf("%d %d", &a, &b);
            insert(root, newNode(b, a));
        }
        else
            print(remove(root, (n+1)%2));
    }
	return 0;
}

